package cn.edu.xjtu.competiton.力扣.周赛.weekly292;

import cn.edu.xjtu.Util.TreeNode.TreeNode;

/**
 * @author Hydrion-QLz
 * @date 2022-05-08 10:46
 * @description https://leetcode-cn.com/contest/weekly-contest-292/problems/count-nodes-equal-to-average-of-subtree/
 * <p>
 * 给你一棵二叉树的根节点 root ，找出并返回满足要求的节点数，要求节点的值等于其 子树 中值的 平均值 。
 * <p>
 * 注意：
 * <p>
 * n 个元素的平均值可以由 n 个元素 求和 然后再除以 n ，并 向下舍入 到最近的整数。
 * root 的 子树 由 root 和它的所有后代组成。
 */
public class second {
    int count = 0;

    public int averageOfSubtree(TreeNode root) {
        postorder(root);
        return count;
    }

    private int[] postorder(TreeNode root) {
        if (root == null) {
            return new int[]{0, 0};
        }
        int[] left = postorder(root.left);
        int[] right = postorder(root.right);
        int sum = left[0] + right[0] + root.val;
        int nodeCount = left[1] + right[1] + 1;
        if (root.val == sum / nodeCount) {
            count++;
            System.out.println(root.val);
        }
        return new int[]{sum, nodeCount};
    }
}
